The representation and/or the compression of data, such as images or sound, can generally be divided into two classes. The first class, commonly called "lossless" allows for an exact reconstruction of the original data from the compressed or represented data in the reconstruction or decompression process. Lossless compression normally proceeds by removal of real redundancy in the data and includes such techniques as run length encoding, Huffman coding and LZW coding which are techniques well known to those skilled in the art of compression methods.
A second class of techniques, known as "lossy" techniques represent or compress their data such that, upon decompression or reconstruction, the decompressed or reconstructed data may vary in comparison to the original data. Lossy techniques are able to be used where it is not necessary to exactly reconstruct the original data, with a close approximation to it, in most cases, being suitable. Of course, it will be readily apparent to those skilled in the art that, after initial compression via a lossy technique, the resulting compressed data can be further compressed utilising a lossless technique.
One form of well known lossy image compression utilises the Discrete Cosine Transform (DCT) in order to compress an image as part of a lossy compression system. This system, as defined by the Joint Photographic Experts Group (JPEG) standard has become increasingly popular for the compression of still images. A further standard, known as the MPEG standard developed by Motion Pictures Expert Group, has also become a popular form of video image compression. The MPEG standard also relies on the Discrete Cosine Transform for the compression of images.
An alternative compression or representation system is one based on "fractal" coding. The fractal coding technique relies on the creation of a series of transformations which, when applied to a set of data, result in that data approaching a "fixed point" which approximates the original data which is desired to be displayed. Therefore, in order to regenerate an approximation of the data utilising fractal techniques, it is only necessary to know the nature and content of the transformations as, given some initial arbitrary data, the transformations can be applied to that data in an iterative process such that the arbitrary data is transformed into a close approximation of the original data.
As, the data can be represented by its transformations, fractal coding techniques offer the opportunity to produce substantial compression of data and, in particular, offer the opportunity to produce a better compression system than the JPEG standard. Examples of fractal compression or representation techniques can be seen from PCT Publication No. WO 93/17519 entitled "Fractal Coding of Data" by Monro and Dudbridge, in addition to "Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations" by A. E. Jacquin published in IEEE Transactions on Image Processing, 1, pages 18-30, (1990).
The iterated nature of producing a final image through the continuous utilisation of transformations has led to fractal coding techniques being described as an "Iterated Function System (IFS)". The transformations utilised in the IFS are commonly of a contractive nature in that the application of a transform results in the data "contracting" to a final set of data in accordance with a "difference measure" which can be a Root Mean Square (RMS) measure or a Hausdorff distance measure, known to those skilled in the art.
Although the discussion will hereinafter be continued in relation to images, it will be readily apparent to those skilled in the art that the present invention is not limited to images and is readily applicable to any form of data for which a fractal representation or compression is desired. Furthermore, although two dimensional data is referred to in the following description, lower and higher dimensional data sets can easily be accommodated with analogous methods by those skilled in the art.
Referring now to FIGS. 1 and 2, the prior art iterated functions systems normally operate by partitioning an initial image 1 into a number of range blocks 2 which completely tile or cover the initial image 1.
In the system set out in the aforementioned article by Jacquin, the pixels in each range block 2 are approximated by a linear combination of a first element which is derived from a range base function which is defined by Jacquin to be of uniform intensity. The second portion of each pixel of a range block 2 is made up of pixels derived from a transformation of pixels belonging to some other part of the image. These other portions of the image, which can be derived utilising a number of different methods, are known as "domain" blocks. These domain blocks are transformed utilising carefully selected affine transformation functions. The affine transformation functions and their selection corresponds to the "fractal" portion of the image and, in the Jacquin system, they are used to modulate each pixel of the range block 2.
In PCT Publication No. WO 93/17519 entitled "Fractal Coding of Data", Monro and Dudbridge describe a system whereby the range base function consists of a planar facet. The range blocks are tiled in their entirety by four domain blocks. The planar facet is "corrected" or modulated by the application of a scaled version of the domain block which is one quarter the area of the original domain block. The major advantage of the Monro and Dudbridge technique is that an extensive search for the most suitable domain block is avoided.